Electronic messaging, particularly electronic mail (e-mail) carried over the Internet, has become a preferred method of communication for many individuals and organizations. Unfortunately, e-mail recipients are increasingly being subjected to unsolicited and unwanted mass mailings. With the growth of Internet-based commerce, a wide and growing variety of electronic merchandisers are repeatedly sending unsolicited mail advertising their products and services to an ever-expanding universe of e-mail recipients. For example, users of the Internet who merely provide their e-mail addresses in response to perhaps innocuous appearing requests for visitor information generated by various web sites, often find, later upon receipt of unsolicited mail and much to their displeasure, that they have been included on electronic distribution lists. This can have a negative effect on the users' experiences and can diminish the productivity of users who receive such unwanted e-mail, or “spam”, at their place of business.
Once a recipient finds himself on an electronic mailing list, that individual cannot readily, if at all, remove his address from it, thus effectively guaranteeing that he or she will continue to receive unsolicited mail. This occurs simply because the sender either prevents a recipient of a message from identifying the sender of that message (such as by sending mail through a proxy server) and hence precludes that recipient from contacting the sender in an attempt to be excluded from a distribution list, or simply ignores any request previously received from the recipient to be so excluded.
An individual can easily receive hundreds or thousands of pieces of unsolicited ordinary postal mail over the course of a year, or less. As bad as that is, given the extreme ease and insignificant cost through which electronic distribution lists can be readily exchanged and e-mail messages disseminated across extremely large numbers of addressees, a single e-mail addressee included on several distribution lists can expect to receive a considerably larger number of unsolicited email messages over a much shorter period of time. Furthermore, while many unsolicited e-mail messages are benign, others, such as pornographic, inflammatory and abusive material, are highly offensive to their recipients. Some (viruses) are even harmful to computers. All such unsolicited messages collectively constitute so-called “junk” mail or “spam”.
One proposed method of addressing the junk-email problem requires a digital “postage stamp” to be attached to an e-mail message. More generally, these stamps can constitute a “proof-of-work.” The basic idea can be summarized as follows: Whenever a sender transmits e-mail to an intended recipient, a digital postage stamp will be generated. Unlike physical postage, the sender does not spend money but instead spends CPU cycles or other computer system resources by solving a puzzle, the solution to which becomes a postage stamp. The theory is that the economics of bulk e-mail changes when e-mail is required to have postage. A single digital postage stamp is not hard to create, requiring perhaps a few seconds of computing time. Bulk e-mailers, however, rely on being able to send thousands or hundreds of thousands, or more, of messages very quickly; if they need to calculate postage stamps for every message, it will slow them down and consume CPU resources. Making spam more expensive in this manner is intended to deter spammers from operating, since a sender of a bulk e-mail in such a scheme must spend significant computational resources—at a real cost—in order to send a mass mailing, while the cost to each recipient is negligible. Another advantage to putting electronic postage on e-mail is that it can also be used as a key for filtering out spam. By adding an easily detectable and verifiable postage stamp, users would be able to filter out e-mail that does not have this postage stamp.
In some known digital postage systems, the stamp takes the form of a cryptographic puzzle and solution. The puzzles are mathematical problems possessing the general quality that they are moderately difficult to solve (i.e., they require more than a nominal amount of time and computing power), yet are easy to verify once the solution is in hand. Several researchers have investigated mathematical functions with the desired qualities, as well as protocols and systems for effectuating the use of cryptographic puzzles as digital postage stamps. These researchers include: Dwork and Naor, who proposed the use of cryptographic puzzles as a deterrent to unwanted email (“Pricing via Processing or Combatting Junk Mail,” Lecture Notes in Computer Science 740 (Proceedings of CRYPTO '92), 1993, pp. 137-147; Adam Back, who later proposed Hash Cash for use in protecting mailing lists and in stopping denial-of-service attacks (see “Hashcash—a Denial of Service Counter-Measure, August 2002, available from http://cypherspace.org/˜adam/hashcash/); Abadi, et al., who researched particularly useful mathematical functions (“Moderately Hard, memory-bound Functions”, Proceedings of the 10th Annual Network and Distributed System Security Symposium, February 2003); and Dwork et al., who conducted similar research (“On Memory-Bound Functions for Fighting Spam”, Proceedings of the 23rd Annual International Cryptology Conference (CRYPTO 2003), August 2003). The above references are hereby incorporated by reference in their entirety for all that they teach without exclusion of any parts thereof.
One problem with digital postage is ensuring that a cryptographic puzzle-solution used as a stamp for one email message cannot be re-used as a stamp for a second email message. If puzzle-solutions are allowed to be re-used, an ill-intended email sender could copy one puzzle-solution for use in multiple messages, and the recipients would have no way of knowing these messages were illegitimate. Some existing digital postage systems, such as those of the aforementioned Dwork-Naor and HashCash, address this problem by insisting that the puzzle be a mathematical function of the message itself. The puzzle-solution in such systems is thus uniquely tied to the message. Although these systems preclude a puzzle-solution from being re-used, they necessarily require that the message has already been composed prior to the puzzle-solution's creation.
Other known digital postage systems address this limitation by use of a “ticket server.” The ticket server is a centralized server that generates cryptographic puzzles offline. An email sender obtains a ticket by, for example, solving a cryptographic puzzle. The ticket is attached to an email message intended for a recipient, who then verifies the ticket's validity by checking with the centralized ticket server. The ticket server “cancels” used tickets to ensure that the same ticket cannot be used more than once. Although these systems allow for creating digital postage prior to message composition, they require the email sender and recipient to use and trust the same centralized server. Such a ticket server system is described by M. Abadi, A. Birrell, M. Burrows, F. Dabek, and T. Wobber, in Bankable Postage for Network Services, Proceedings of the 8th Asian Computing Science Conference, Mumbai, India, December 2003, which is hereby incorporated by reference in its entirety for all that it teaches without exclusion of any part thereof.